#include <stdio.h>
#include <stdlib.h>
#include <windows.h>

// 定义三元组结构体
typedef struct {
    int row;  // 行号
    int col;  // 列号
    int value;  // 元素值
} Triple;

// 稀疏矩阵的转置函数
void transpose(int m, int n, int t, Triple *A, Triple *B) {
    // 初始化辅助数组
    int *num = (int *)malloc(n * sizeof(int));
    int *cpot = (int *)malloc(n * sizeof(int));
    for (int j = 0; j < n; j++) {
        num[j] = 0;
    }
    
    // 计算每一列的非零元素个数
    for (int k = 0; k < t; k++) {
        num[A[k].col]++;
    }

    // 计算每一列第一个非零元素在B中的位置
    cpot[0] = 0;
    for (int j = 1; j < n; j++) {
        cpot[j] = cpot[j - 1] + num[j - 1];
    }

    // 转置过程
    for (int k = 0; k < t; k++) {
        int pb = cpot[A[k].col];
        B[pb].row = A[k].col;
        B[pb].col = A[k].row;
        B[pb].value = A[k].value;
        cpot[A[k].col]++;
    }

    free(num);
    free(cpot);
}

// 打印稀疏矩阵
void printSparseMatrix(int m, int n, int t, Triple *matrix) {
    printf("稀疏矩阵：\n");
    printf("行数：%d，列数：%d，非零元素个数：%d\n", m, n, t);
    printf("行 列 值\n");
    for (int i = 0; i < t; i++) {
        printf("%2d  %2d  %2d\n", matrix[i].row, matrix[i].col, matrix[i].value);
    }
}

int main() {
    SetConsoleOutputCP(65001);
    int m = 4, n = 5, t = 6; // 稀疏矩阵的行数、列数和非零元素个数
    Triple A[6] = {{0, 1, 3}, {0, 3, 4}, {1, 2, 5}, {2, 0, 1}, {2, 3, 2}, {3, 3, 6}}; // 稀疏矩阵A
    Triple B[6]; // 转置后的稀疏矩阵B

    printSparseMatrix(m, n, t, A);
    transpose(m, n, t, A, B);
    printSparseMatrix(n, m, t, B);

    return 0;
}
